class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> v;
        if (root == nullptr)
        {
            return v;
        }
        stack<TreeNode*> t;
        TreeNode* cur = root;
        while (cur || !t.empty())
        {
            while (cur)
            {
                v.push_back(cur->val);
                t.push(cur);
                cur = cur->left;
            }

            cur = t.top()->right;
            t.pop();
        }
        return v;
    }
};